package org.apache.commons.graph.model

import com.gitee.wsl.ext.list.addFirst
import com.gitee.wsl.ext.list.addLast
import com.gitee.wsl.text.format.format
import org.apache.commons.graph.Path
import org.apache.commons.graph.bean.DefaultEdge
import org.apache.commons.graph.bean.VertexPair
import org.apache.commons.graph.utils.Assertions
import org.apache.commons.graph.utils.Objects

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Support [Path] implementation, optimized for algorithms (such Dijkstra's) that need to rebuild the path
 * traversing the predecessor list bottom-up.
 *
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
</E></V> */
open class InMemoryPath<V, E>(start: V, target: V) : Path<V, E> {
    /**
     * {@inheritDoc}
     */
    override val source: V = Assertions.checkNotNull(start, "Path source cannot be null")

    /**
     * {@inheritDoc}
     */
    override val target: V = Assertions.checkNotNull(target, "Path target cannot be null")

    override val vertices = mutableListOf<V>()

    override val edges  = mutableListOf<E>()

    private val successors: MutableMap<V, V> = HashMap()

    private val indexedEdges: MutableMap<VertexPair<V>, E> = HashMap()

    private val indexedVertices: MutableMap<E, VertexPair<V>> = HashMap()

    private fun addConnection(head: V, edge: E, tail: V) {
        successors[head] = tail

        val vertexPair = VertexPair(head, tail)
        indexedEdges[vertexPair] = edge
        indexedVertices[edge] = vertexPair
    }

    /**
     * Adds the edge in head.
     *
     * @param head the head vertex
     * @param edge the edge
     * @param tail the tail vertex
     */
    open fun addConnectionInHead(head: V, edge: E, tail: V) {
        if (target == tail) {
            vertices.addFirst(tail)
        }

        vertices.addFirst(head)
        edges.addFirst(edge)

        addConnection(head, edge, tail)
    }

    /**
     * Adds the edge in tail.
     *
     * @param head the head vertex
     * @param edge the edge
     * @param tail the tail vertex
     */
    open fun addConnectionInTail(head: V, edge: E, tail: V) {
        vertices.addLast(head)
        edges.addLast(edge)

        if (target == tail) {
            vertices.addLast(tail)
        }

        addConnection(head, edge, tail)
    }

    /**
     * {@inheritDoc}
     */
    override fun containsEdge(e: E): Boolean {
        return edges.contains(e)
    }

    /**
     * {@inheritDoc}
     */
    override fun containsVertex(v: V): Boolean {
        return vertices.contains(v)
    }

    /**
     * {@inheritDoc}
     */
    override fun equals(other: Any?): Boolean {
        if (this === other) {
            return true
        }

        if (other == null || this::class != other::class) {
            return false
        }

        other as InMemoryPath<*, *>

        return source==other.source
                && target== other.target
                && vertices == other.vertices
                && edges == other.edges
    }

    /**
     * {@inheritDoc}
     */
    override fun getConnectedVertices(v: V): Iterable<V> {
        var v = v
        v = Assertions.checkNotNull(v, "Impossible to get the degree of a null vertex")

        if (target == v) {
            return emptyList()
        }

        Assertions.checkArgument(
            successors.containsKey(v),
            "Impossible to get the degree of input vertex; %s not contained in this path", v
        )

        val connected= successors[v]?:return emptyList()
        // type driven by input type
        return listOf(connected)
    }

    /**
     * {@inheritDoc}
     */
    override fun getDegree(v: V): Int {
        var v = v
        v = Assertions.checkNotNull(v, "Impossible to get the degree of a null vertex")
        Assertions.checkArgument(
            successors.containsKey(v),
            "Impossible to get the degree of input vertex; %s not contained in this path", v
        )

        if (source == v || target == v) {
            return 1
        }

        return 2
    }

    /**
     * {@inheritDoc}
     */
    override fun getEdge(source: V, target: V): E? {
        return indexedEdges[VertexPair(source, target)]
    }

    /**
     * {@inheritDoc}
     */
//    fun getEdges(): Iterable<E> {
//        return edges
//    }

    override val order: Int
        /**
         * {@inheritDoc}
         */
        get() = vertices.size

    override val size: Int
        /**
         * {@inheritDoc}
         */
        get() = edges.size

    /**
     * {@inheritDoc}
     */
//    fun getVertices(): Iterable<V> {
//        return Collections.unmodifiableList(vertices)
//    }

    /**
     * {@inheritDoc}
     */
    override fun getVertices(e: E): VertexPair<V>? {
        return indexedVertices[e]
    }

    /**
     * {@inheritDoc}
     */
    override fun hashCode(): Int {
        val prime = 31
        return Objects.hash(1, prime, edges, source, target, vertices)
    }

    /**
     * {@inheritDoc}
     */
    override fun toString(): String {
        return String.format("InMemoryPath [vertices=%s, edges=%s]", vertices, edges)
    }

}

fun<V, E> Path.Companion.inMemoryPath(start: V, target: V) = InMemoryPath<V, E>(start, target)

typealias SampleInMemoryPath<V> = InMemoryPath<V, DefaultEdge<V>>

fun<V> Path.Companion.sampleInMemoryPath(start: V, target: V) = SampleInMemoryPath(start, target)